package com.kiven.quicksort;

import java.util.*;


/**
 * 非递归方法实现快速排序的功能
 * 	   借助堆栈(stack)作为辅助工具，每经过1次划分，就把左边的子数组的左右指针(实际上是记录数组下标的两个整数)压入栈中，
 *   对右边的字数组继续划分，直到右边的子数组的左右指针满足：left >= right,弹栈，接着再重复上面的工作，划分、压栈...
 *   
 * @author liqingwen
 *
 */

public class NoRecursionQuickSort {
	
	/**
	 * 该方法在获得一轮快速排序后的分界点，也就是轴点的下标
	 * 
	 * @param oldNums 排序的数组
	 * @param left	数组的起始下标
	 * @param right 数组的长度
	 * @return position 轴点的位置
	 */
	public int position(int[] oldNums,int left,int right) {
		int leftPtr = left-1;  //leftPtr指向数组的头元素，每次初始化时，现有
		int rightPtr = right;	//数组的尾元素
		int pivotValue = oldNums[right]; //尾元素作为轴点
		
		while(true) {
			while(oldNums[++leftPtr] < pivotValue);  //从左边开始扫描，找到大于轴点数的元素
			while(rightPtr > leftPtr && oldNums[--rightPtr] > pivotValue); //从右边开始扫描，找到小于轴点数的元素
			
			//先对指针进行判断
			if(leftPtr >= rightPtr) break;
			else {
				//满足条件时，对元素的值进行交换
				int temp = oldNums[leftPtr];
				oldNums[leftPtr] = oldNums[rightPtr];
				oldNums[rightPtr] = temp;
			}
		}
		
		//得到一次快速排序后的位置
		int temp = oldNums[leftPtr];
		oldNums[leftPtr] = oldNums[right];
		oldNums[right] = temp;
		
		return leftPtr;
	}
	
	/**
	 * 此方法是利用堆栈实现非递归的方法对数组进行快速排序
	 * 
	 * @param arrs 待排序数组
	 * @param left 数组头元素下标值
	 * @param right 数组未元素下标值
	 */
	public void sort(int[] arrs,int left,int right) {
		LinkedStack ls = new LinkedStack();
		int[] ints = arrs;
		int i = left;  //表示数组头元素的下标地址
		int j = right;  //表示数组尾元素的下标地址
		int p = -1;
		
		while(true) {
			//得到一次快速排序后的轴点最终的位置
			p = position(ints,i,j);
			
			//对返回的最终的轴点的位置进行判断，如果轴点左边有两个或两个以上，左边的这些元素还的进行排序，所以线将要排序的数组元素的最左边和最后边的下标压入堆栈内
			 
			if(p-i>1) {
				ls.push(i, p-1);
			}
			
			//右边的数组元素继续排序
			i = p+1;
			
			//控制是否接着排序，当下面的条件成立时，说明此时的排序结束
			if(i >= j) {
				/*
				 * 当前进行排序的子数组结束排序时，去堆栈中查找是否存在为排序完的子数组
				 * 如果存在，则将该子数组节点弹出
				 */
				if(!ls.isEmpty()) {
					Node node = ls.pop();
					i = node.getLeft();
					j = node.getRight();
				}
				else break;
			}
		}
	}
	
	
	public static void main(String[] args) {
		NoRecursionQuickSort qs = new NoRecursionQuickSort();
		int[] arrs = new int[30];
		for(int i=0; i<arrs.length; i++) {
			arrs[i] = new Random().nextInt(100);
		}
		qs.sort(arrs, 0, arrs.length-1);
		for(int i : arrs) {
			System.out.print(i + " ");
		}
	}
}
